public class Test {
    /*
    题目 1：数组中的逆序对
     */
    static int count = 0;
    public static int InversePairs(int [] array) {
        //长度小于 2 ，则无逆序
        if(array.length < 2){
            return 0;
        }

        //进入归并
        mergeSort(array,0,array.length - 1);
        return count;
    }

    private static void mergeSort(int[] array,int left,int right){
        //找到分割点
        //这是一个小技巧
        //防止 int 越界
        int mid = left + (right - left)/2;
        if(left < right){
            //左子数组
            mergeSort(array,left,mid);
            //右子数组
            mergeSort(array,mid + 1, right);
            //合并
            merge(array, left, mid, right);
        }
    }

    public static void merge(int[] array, int left, int mid, int right){
        // 创建临时数组，长度为此时两个子数组加起来的长度
        int[] arr = new int[right - left + 1];
        // 临时数组的下标起点
        int c = 0;
        // 保存在原数组的起点下标值
        int s = left;
        // 左子数组的起始指针
        int l = left;
        //右子数组的起始指针
        int r = mid + 1;
        while(l <= mid && r <= right){
            // 当左子数组的当前元素小的时候，跳过，无逆序对
            if(array[l] <= array[r]){
                arr[c] = array[l];
                c++;
                l++;
            }else{
                arr[c] = array[r];
                count += mid - l + 1;
                count %= 1000000007;
                c++;
                r++;
            }
        }

        // 左子数组还有元素时，全部放入临时数组
        while(l <= mid){
            arr[c++] = array[l++];
        }

        // 右子数组还有元素时，全部放入临时数组
        while(r <= right){
            arr[c++] = array[r++];
        }

        // 将临时数组中的元素放入到原数组的指定位置
        for(int num : arr){
            array[s++] = num;
        }
    }

    public static void main1(String[] args) {
        int[] arr = {8,7,6,5,4,3,2,1};
        int res = InversePairs(arr);
        System.out.println(res);
    }

    /*
    题目 2：比较版本号
     */
    
}
